package everything.search.agents;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import everything.Agent;
import everything.Flag;
import everything.WorldMap;
import everything.search.AgentState;
import everything.search.trees.GameTreeNormalSearch;
import everything.search.trees.GameTreeSearch;
import everything.search.trees.nodes.GameTreeNode;

public class IntelligentAgent extends Agent{

	Agent _opponent;
	int _plys;
	boolean _memorize;

	public IntelligentAgent(String name, String color, int x, int y, WorldMap map, int plys, boolean memorize, int id) {
		super(name, color, x, y, map, id);
		_plys = plys;
		_memorize = memorize;
	}

	public void initOpponent(Agent opponent){
		_opponent = opponent;
		System.out.println("My opponent is " + opponent.getName() +"! Good Luck !");
	}

	@Override
	public void makeMove() {
		GameTreeSearch game = new GameTreeNormalSearch(_map, _id, _opponent.getId());
		makeMove2(game);
	}

	public void makeMove2(GameTreeSearch game) {
		List<Flag> flagList = _map.getFlagList();
		AgentState state = new AgentState(_xLocation,_yLocation,(_onIce ? _orientation : null),_bullets,!_isGhost,_opponent.getX(),_opponent.getY(),_opponent.getSlidingDirection(),_opponent.getBullets(),!_opponent.isGhost(), flagList.toArray(new Flag[flagList.size()]), _map.getMovesLeft());
		GameTreeNode finalMove = game.search(state, _plys, _memorize);
		GameTreeNode node = finalMove;
		// getting first move from top of tree
		while (node.getParent()!=null){
			if (node.getParent().getParent() == null) {
				move(node.getMove());
				break;
			}
			node = node.getParent();
		}
	}



	public static double utility(int id, AgentState t, WorldMap map) {
		if (t.isTerminal()){
		//if (t.getRemainingMoves()==0){
			int myScore=0;
			int opScore=0;
			Flag[] flags = t.getFlags();
			for (int i =0; i<flags.length; i++){
				if (flags[i].getOwner()==id){
					myScore+=flags[i].getValue();
				} else if (flags[i].getOwner()!=0){
					opScore+=flags[i].getValue();
				}
			}
			return myScore - opScore;
		}
//		int count = 0;
//		for (int i=0; i<t.getFlags().length; i++){
//			if (t.getFlags()[i].getOwner()!=0){
//				count++;
//			}
//		}
//		if (count>1)
//			System.out.println(t);
		return estimation(id, t, map);
	}


	public static double estimation(int id, AgentState t, WorldMap map){
		FlagQueue[] flags = processFlags(id, t.getX(), t.getY(), t.getHealth(), t.getXOpponent(), t.getYOpponent(), t.getHOpponent(), t.getRemainingMoves(), t.getFlags(), map);
		if (!t.getHOpponent()){
			//compute all flags that we can take in the remaining moves
			//System.out.println("A " + flags[0].totalScore + "  " + flags[0].totalMoves);
			return flags[0].currentScore - flags[1].currentScore + flags[0].totalScore-flags[0].totalMoves/10000.0 + (flags[0].totalScore!=0 ? (0.005+t.getRemainingMoves()/100.0) : 0) + t.getRemainingMoves()/100.0;

		} else if (!t.getHealth()){
			//do same with opponent - but with minus
			//System.out.println("B " + flags[1].totalScore + "  " + flags[1].totalMoves);
			return flags[0].currentScore - flags[1].currentScore - (flags[1].totalScore-flags[1].totalMoves/10000.0 + (flags[1].totalScore!=0 ? (0.005+t.getRemainingMoves()/100.0) : 0)) + t.getRemainingMoves()/100.0;
		} else {
			//return the difference between the flags we can take
			//System.out.println("C " + flags[0].totalScore + "  " + flags[0].totalMoves + "  OP - " + flags[0].totalScore + "  " + flags[0].totalMoves);
			return flags[0].currentScore - flags[1].currentScore + (flags[0].totalScore-flags[0].totalMoves/10000.0) - (flags[1].totalScore-flags[1].totalMoves/10000.0) + t.getRemainingMoves()/100.0 + t.getBullets()/1000.0 - t.getBOpponent()/1000.0;
		}
	}

	static class FlagQueue extends LinkedList<Flag>{
		private static final long serialVersionUID = 1L;
		int totalScore;
		int totalMoves;
		int currentScore;
	}

	/*
	 * returns 2 queues of flags, the flags that the first agent can get to first
	 * and the flags that the second agent can get to first (using BFS)
	 */
	public static FlagQueue[] processFlags(int id, int startXPosition, int startYPosition, boolean health, int opStartXPosition, int opStartYPosition, boolean opHealth, int remainingMoves, Flag[] flags, WorldMap map){
		List<Flag> flagsCopy = new LinkedList<Flag>();


		int currentScore = 0;
		int currentOpScore = 0;
		for (int i =0 ; i<flags.length ; i++){
			if (flags[i].getOwner()==0){
				Flag f = new Flag(flags[i].getX(), flags[i].getY(), flags[i].getValue());
				f.setOwner(flags[i].getOwner());
				flagsCopy.add(f);
			} else if (flags[i].getOwner()==id){
				currentScore=currentScore+flags[i].getValue();
			} else {
				currentOpScore=currentOpScore+flags[i].getValue();
			}
		}
		FlagQueue[] ans = new FlagQueue[2];
		ans[0]  = new FlagQueue();
		ans[1]  = new FlagQueue();

		int xPosition = startXPosition;
		int yPosition = startYPosition;
		int opXPosition = opStartXPosition;
		int opYPosition = opStartYPosition;
		int totalDist = 0;
		int totalOpDist = 0;
		int totalScore = 0;
		int totalOpScore = 0;

		if (!health && !opHealth) return ans;
		//System.out.println("Flag setup: [" +startXPosition + "," + startYPosition + "]");
		while(!flagsCopy.isEmpty()){
			Flag closestFlag = flagsCopy.get(0);
			Flag closestOpFlag = flagsCopy.get(0);
			int minDist = countMoves(xPosition, yPosition, closestFlag.getX(), closestFlag.getY(), health, map);
			int minOpDist = countMoves(opXPosition, opYPosition, closestOpFlag.getX(), closestOpFlag.getY(), opHealth, map);
			for (Flag flag : flagsCopy) {
				int dist = countMoves(xPosition, yPosition, flag.getX(), flag.getY(), health, map);
				int opDist = countMoves(opXPosition, opYPosition, flag.getX(), flag.getY(), opHealth, map);
				if (dist < minDist){
					minDist = dist;
					closestFlag = flag;
				}
				if (opDist < minOpDist){
					minOpDist = opDist;
					closestOpFlag = flag;
				}
			}
			//both players cant collect flags
			if ((totalDist + minDist > remainingMoves || !health) && (totalOpDist + minOpDist > remainingMoves || !opHealth)) break;
			if (!opHealth || (health && totalDist+minDist <= totalOpDist + minOpDist)){
				ans[0].add(closestFlag);
				flagsCopy.remove(closestFlag);
				xPosition = closestFlag.getX();
				yPosition = closestFlag.getY();
				totalDist = totalDist + minDist;
				totalScore = totalScore + closestFlag.getValue();
			} else {
				ans[1].add(closestOpFlag);
				flagsCopy.remove(closestOpFlag);
				opXPosition = closestOpFlag.getX();
				opYPosition = closestOpFlag.getY();
				totalOpDist = totalOpDist + minOpDist;
				totalOpScore = totalOpScore + closestOpFlag.getValue();
			}
		}
		ans[0].totalMoves = totalDist;
		ans[0].totalScore = totalScore;
		ans[0].currentScore = currentScore;
		ans[1].totalMoves = totalOpDist;
		ans[1].totalScore = totalOpScore;
		ans[1].currentScore = currentOpScore;
		return ans;
	}

	public static int countMoves(int x, int y, int destX, int destY, boolean health, WorldMap map){
		int height = map.getHeight();
		int width = map.getWidth();
		if (destX==x && destY==y) return 0;

		// Initializations
		int[][] board_prev = new int[height][];
		int[][] board_dist = new int[height][];
		int maxlength = height*width;
		for (int i=0 ; i<board_prev.length; i++){
			board_prev[i] = new int[width];
			board_dist[i] = new int[width];
			for(int j=0; j<board_prev[i].length; j++){
				board_prev[i][j] = 0;			// Previous node in optimal path from source
				board_dist[i][j] = maxlength;	// Unknown distance function from source to v
			}
		}
		board_dist[x][y] = 0;					// Distance from source to source
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(new Integer(x*width+y+1));
		while (!Q.isEmpty() && board_prev[destX][destY]==0){
			int cell = Q.poll().intValue();
			int tmpX = cell / width;
			int tmpY = cell % width - 1;

			if (!(map.brickStatus(tmpX+1, tmpY) == WorldMap.WALL) && board_prev[tmpX+1][tmpY]==0){
				Q.add(new Integer((tmpX+1)*width+(tmpY)+1));
				board_prev[tmpX+1][tmpY] = cell;
				board_dist[tmpX+1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX, tmpY+1) == WorldMap.WALL) && board_prev[tmpX][tmpY+1]==0){
				Q.add(new Integer((tmpX)*width+(tmpY+1)+1));
				board_prev[tmpX][tmpY+1] = cell;
				board_dist[tmpX][tmpY+1] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX-1, tmpY) == WorldMap.WALL) && board_prev[tmpX-1][tmpY]==0){
				Q.add(new Integer((tmpX-1)*width+(tmpY)+1));
				board_prev[tmpX-1][tmpY] = cell;
				board_dist[tmpX-1][tmpY] = board_dist[tmpX][tmpY]+1;
			}
			if (!(map.brickStatus(tmpX, tmpY-1) == WorldMap.WALL) && board_prev[tmpX][tmpY-1]==0){
				Q.add(new Integer((tmpX)*width+(tmpY-1)+1));
				board_prev[tmpX][tmpY-1] = cell;
				board_dist[tmpX][tmpY-1] = board_dist[tmpX][tmpY]+1;
			}
		}
		if (board_prev[destX][destY]==0 || !health){
			return maxlength;
		} else {
			return board_dist[destX][destY];
		}
		//		Q := the set of all nodes in Graph    // All nodes in the graph are unoptimized - thus are in Q
		//		while Q is not empty:                 // The main loop
		//		u := node in Q with smallest dist[]
		//		remove u from Q
		//		for each neighbor v of u:         // where v has not yet been removed from Q.
		//		alt := dist[u] + dist_between(u, v)       // be careful in 1st step - dist[u] is infinity yet
		//		if alt < dist[v]              // Relax (u,v)
		//		dist[v] := alt
		//		previous[v] := u
		//		return previous[]
	}

	public static void main(String[] args){
	}

}
